#include"HashTable.h"

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
    typedef const K T;  // 为了防止数据，这里加上const
    struct ExtractK
    {
        // 参数 const T& 展开就是 const const K&
        // const重复修饰同一个类型时，编译器会将其视为冗余，最终类型不变
        // const const K&等价于 const K&
        const K& operator() (const T& x) const
        {
            return x;
        }
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;
public:
    unordered_set() {}
    unordered_set(initializer_list<T> il)
    {
        _ht.reserve(ceil(il.size() / 0.7));
        for(const auto& e : il)
            _ht.insert(e);
    }

    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator const_iterator;
    iterator begin() { return _ht.begin(); }
    iterator end()   { return _ht.end(); }
    const_iterator begin() const { return _ht.begin(); }
    const_iterator end() const   { return _ht.end(); }

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }
    
    size_t size() const { return _ht.size(); }
    bool empty() const { return _ht.empty(); }
    void reserve(size_t n) {_ht.reserve(n); }
    void clear() { _ht.clear(); }
    void swap(unordered_set& s) { _ht.swap(s._ht); }
};

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
    typedef pair<const K, V> T;  // 为了防止数据，键值加上const
    struct ExtractK
    {
        const K& operator() (const T& x) const
        {
            return x.first;
        }
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;

public:
    unordered_map() {}
    unordered_map(initializer_list<T> il) 
    {
        _ht.reserve(ceil(il.size() / 0.7));
        for(const auto& e : il)
            _ht.insert(e);
    }
    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator const_iterator;
    iterator begin() { return _ht.begin(); }
    iterator end()   { return _ht.end(); }
    const_iterator begin() const { return _ht.begin(); }
    const_iterator end() const   { return _ht.end(); }

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }

    // 通过key找对应的值。
    V& operator[] (const K& key)
    {
        return insert({key, V()}).first->second;
    }

    size_t size() const { return _ht.size(); }
    bool empty() const  { return _ht.empty(); }
    void reserve(size_t n) { _ht.reserve(n); }
    void clear()    { _ht.clear(); }
    void swap(unordered_map& s) { _ht.swap(s._ht); }
};